#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cache.h"

//shzb: cache buffer statistics
int buffer_cnt = 0;
int buffer_hit = 0;
//shzb:cache algorithm
int cache_min;
//cache_type define extern in h
int cache_type=1;
/***********************************
statistics for cache read/write count
************************************/
int buffer_miss_cnt=0;
int buffer_write_hit=0;
int buffer_write_miss=0;
int buffer_read_miss=0;
int buffer_read_hit=0; 
/***********************************************************************
  Cache temp variable
 ***********************************************************************/
int cache_lru_min = 9999999;
int cache_lru_max = 0;
int cache_clru_min = 9999999;
int cache_clru_max = 0;
int cache_dlru_min = 9999999;
int cache_dlru_max = 0;
/***********************************************************************
	some variable replace for callFsim return delay
************************************************************************/
double readFromFlash=0.0005;
double writeToFlash=0.001;
int ftl_type=3;
int cache_max_size=CACHE_MAX_ENTRIES;
/*******************************************
		initialize operation
*******************************************/
void init_arr()
{
	memset(cache_lru_arr,-1,sizeof(cache_lru_arr));
	memset(cache_dlru_arr,-1,sizeof(cache_clru_arr));
	memset(cache_clru_arr,-1,sizeof(cache_clru_arr));
	cache_clru_cur_size=0;
	cache_dlru_cur_size=0;
}

int opm_init(int blk_num)
{
	int i;
	opagemap_num = blk_num * PAGE_NUM_PER_BLK;
	//allocate memory for struct point opagemap
	opagemap = (struct opm_entry *) malloc(sizeof (struct opm_entry) * opagemap_num);
	//check allocate success?
	if(opagemap==NULL){
		return -1;
	}
	//initialize memory 
	memset(opagemap,0xFF,sizeof(struct opm_entry)*opagemap_num);
	TOTAL_MAP_ENTRIES = opagemap_num;
	for(i = 0; i<TOTAL_MAP_ENTRIES; i++){
    opagemap[i].cache_status = 0;
    opagemap[i].cache_age = 0;
    opagemap[i].cache_update = 0;
    opagemap[i].map_status = 0;
    opagemap[i].map_age = 0;
    opagemap[i].update = 0;
  }
  //initialize variables
   CACHE_NUM_ENTRIES= 0;
   CACHE_CLRU_NUM_ENTRIES=0;
   CACHE_DLRU_NUM_ENTRIES=0;
  return 0;
}
/******************************************
	operation for (clr dlru lru)arrary
******************************************/
//check clru_arr and dlru_arr nozero count
int ComputeArrSize(int *arr,int MaxSize)
{
	int index=0;
	int count=0;
	while(index<MaxSize)
	{
		if(arr[index]!=0)
			count++;
		index++;
	}
	return count;
}
//this function is designed for find free position in array
int find_free_pos( int *arr, int size)
{
    int i;
    for(i = 0 ; i < size; i++) {
        if(arr[i] == -1) {
            return i;
        }
    } 
    printf("shouldn't come here for find_free_pos()\n");
    exit(1);
    return -1;
}
//the function is to find (lru,clru,dlru)arr cache age min index(LRU position)
int find_cache_min(int arr[],int arrMaxSize)
{
  int i; 
  int temp = 99999999;
  int cache_min=-1;
  for(i=0; i < arrMaxSize ;i++) {
  	//attention!!! arr[i]=-1,the opagemap[-1]!!!should slove!!
      if(opagemap[arr[i]].cache_age <= temp) {
          cache_min = arr[i];
          temp = opagemap[arr[i]].cache_age;
      }
  }
   return cache_min;
}
//this function to find the max age in (lru ,clru,dlru)array
int find_cache_max(int arr[],int arrMaxSize)
{
	int i;
	int temp=-1;
	int cache_max=-1;
	for(i=0;i<arrMaxSize;i++){
	//attention!!! arr[i]=-1,the opagemap[-1]!!!should slove!!
		if(opagemap[arr[i]].cache_age>=temp){
			cache_max=arr[i];
			temp=opagemap[arr[i]].cache_age;
		}
	}
	return cache_max;
}
//search_table这个函数搜索输入数组,匹配其数组中的值是否存在val,存在返回在数组的位置i,否则返回-1
int search_table(int *arr, int size, int val) 
{
    int i;
    for(i =0 ; i < size; i++) {
        if(arr[i] == val) {
            return i;
        }
    }
    //test point
    printf("shouldnt come here for search_table()=%d,%d",val,size);
    for( i = 0; i < size; i++) {
      if(arr[i] != -1) {
        printf("arr[%d]=%d ",i,arr[i]);
      }
    }
    exit(1);
    return -1;
}

/***************************************
	calculate delay operation
***************************************/
//duchenjie:cache algortihm，延迟用于计算出缓存的平均响应时间
double calculate_delay_cache()
{
	double delay;
	double cache_read_delay, cache_write_delay;

	cache_read_delay=(double)CACHE_READ_DELAY * cache_read_num;
	cache_write_delay=(double)CACHE_WRITE_DELAY * cache_write_num;

	delay=cache_read_delay + cache_write_delay;

	reset_cache_stat();

	return delay;
}

//reset cache state
void reset_cache_stat()
{
	cache_read_num = 0;
	cache_write_num = 0;
}





//cache algortihm
//return the cache operation delay(double)
double cacheManage(unsigned int secno, int scount, int operation)//缓存管理算法
{
	//define improtant variable
	double delay, flash_delay = 0, cache_delay = 0;
	int bcount,entry_count;
	unsigned int blkno,pageno;
	int cnt;
    int flags;
    //vicitm_page is delete entry
    int vicitm_page_index=-1;
    //add_index is new to array free pos
    int free_pos=-1;
    /*****embed into flashsim should add fllow sentence******/
	// 	int page_pos = -1;
	// if(ftl_type ==1){}
	// //ftl_type=3表示采用的是DFTL算法,存在二级地址(page_num_for_2nd_map_table)的计算
	// if(ftl_type == 3) {
	//     page_num_for_2nd_map_table = (opagemap_num / MAP_ENTRIES_PER_PAGE);
    
 //    	if(youkim_flag1 == 0 ) {
	// 		youkim_flag1 = 1;
 //        	init_arr();
 //    	}

 //    	if((opagemap_num % MAP_ENTRIES_PER_PAGE) != 0){
	// 		page_num_for_2nd_map_table++;
 //    	}
	// }
	//first page alignment
	// page based FTL 
	if(ftl_type == 1 ) { 
	   blkno = secno / 4;
	   bcount = (secno + scount -1)/4 - (secno)/4 + 1;
	}  
	// block based FTL 
	else if(ftl_type == 2){
		blkno = secno/4;
		bcount = (secno + scount -1)/4 - (secno)/4 + 1;
	}
	// o-pagemap scheme
	else if(ftl_type == 3 ) { //注意缓存管理算法的逻辑页号和SDFTL算法中的逻辑页号的区别
		blkno = secno / 4;
//		blkno += page_num_for_2nd_map_table;
		bcount = (secno + scount -1)/4 - (secno)/4 + 1;
	}  
	// FAST scheme
	else if(ftl_type == 4){
		blkno = secno/4;
		bcount = (secno + scount -1)/4 - (secno)/4 + 1;
	}
	//reset cache state for next operation 
	reset_cache_stat();
	//
	cnt = bcount;

	switch(cache_type)
	{
		case 1://LRU algortihm
		while(cnt>0)
		{
			//1-hit cache
			if(opagemap[blkno].cache_status==CACHE_VALID)
			{
				buffer_hit++;
				opagemap[blkno].cache_age=opagemap[cache_lru_max].cache_age+1;
				cache_lru_max=blkno;
				//check request is write?
				if(operation==0){
					opagemap[blkno].cache_update=1;
					cache_write_num++;
				}else{
					cache_read_num++;
				}
			}else{
			//2-hit miss->2.1 cache full and cache is not full
				if(CACHE_NUM_ENTRIES>=cache_max_size){
					//delete the lru(min)
					cache_lru_min=find_cache_min(cache_clru_arr,cache_max_size);
					if(opagemap[cache_lru_min].cache_update!=0){
						//flash_delay+=callFsim(cache_lru_min*4,4,0);
						flash_delay=flash_delay+writeToFlash;
					}
					//delete and reset opagemap related flag
					opagemap[cache_lru_min].cache_age=0;
					opagemap[cache_lru_min].cache_status=CACHE_INVALID;
					opagemap[cache_lru_min].cache_update=0;
					//delete this entry from cache_lru_array
					vicitm_page_index=search_table(cache_lru_arr,cache_max_size,cache_lru_min);
					cache_lru_arr[vicitm_page_index]=-1;
					CACHE_NUM_ENTRIES--;
				}
				//add new blkno into cache
				flash_delay=flash_delay+readFromFlash;
				//change opagemap related flag
				opagemap[blkno].cache_age=opagemap[cache_lru_max].cache_age+1;
				//add this bug !!!!!
				opagemap[blkno].cache_status=CACHE_VALID;
				cache_lru_max=blkno;
				//add into cache_lru_arr 
				free_pos=find_free_pos(cache_lru_arr,cache_max_size);
				//test for debug
				if(free_pos==-1){
					printf("can't find free position for current LPN %d \n",blkno);
					exit(0);
				}
				cache_lru_arr[free_pos]=-1;
				cache_lru_arr[free_pos]=blkno;
				//check request is write?
				if(operation==0){
					opagemap[blkno].cache_update=1;
					cache_write_num++;
				}else{
					cache_read_num++;
				}
				CACHE_NUM_ENTRIES++;
			}
			//search for next LPN(blkno)
			blkno++;
			cnt--;
		}
		break;
		case 2://CASA algortihm
		while(cnt>0)
		{	
			//search for next LPN (blkno)
			blkno++;
			cnt--;
		}
		break;
	}
	//computed cache operation delay
	cache_delay = calculate_delay_cache();//计算缓存的迟延
	//该函数返回的是delay!!!
	delay = flash_delay + cache_delay;//总的迟延=闪存的迟延+缓存的迟延
	return delay;	
}